Tak (function)
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi. It is defined as follows:
τ τ ( x , y , z ) = { τ τ ( τ τ ( x − − 1 , y , z ) , τ τ ( y − − 1 , z , x ) , τ τ ( z − − 1 , x , y ) ) if y < x z otherwise {\displaystyle \tau (x,y,z)={\begin{cases}\tau (\tau (x-1,y,z),\tau (y-1,z,x),\tau (z-1,x,y))&{\text{if }}y<x\\z&{\text{otherwise}}\end{cases}}}
def tak(x: int, y: int, z: int) -> int:
if y < x:
return tak(
tak(x - 1, y, z),
tak(y - 1, z, x),
tak(z - 1, x, y)
)
else:
return z
Contents
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
tak() vs. tarai()
The original definition by Takeuchi was as follows:
def tarai(x: int, y: int, z: int) -> int:
if y < x:
return tarai(
tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y)
)
else:
return y # not z!
tarai is short for たらい回し (tarai mawashi, "to pass around") in Japanese.
John McCarthy named this function tak() after Takeuchi.cite-ref-5[5]
However, in certain later references, the y somehow got turned into the z. This is a small, but significant difference because the original version benefits significantly from lazy evaluation.
Though written in exactly the same manner as others, the Haskell code below runs much faster.
tarai :: Int -> Int -> Int -> Int
tarai x y z
| x <= y = y
| otherwise = tarai (tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)
One can easily accelerate this function via memoization yet lazy evaluation still wins.
The best known way to optimize tarai is to use a mutually recursive helper function as follows.
def laziest_tarai(x: int, y: int, zx: int, zy: int, zz: int) -> int:
if not y < x:
return y
else:
return laziest_tarai(
tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(zx, zy, zz)-1, x, y)
def tarai(x: int, y: int, z: int) -> int:
if not y < x:
return y
else:
return laziest_tarai(
tarai(x-1, y, z),
tarai(y-1, z, x),
z-1, x, y)
Here is an efficient implementation of tarai() in C:
int tarai(int x, int y, int z)
{
while (x > y) {
int oldx = x, oldy = y;
x = tarai(x - 1, y, z);
y = tarai(y - 1, z, oldx);
if (x <= y) break;
z = tarai(z - 1, oldx, oldy);
}
return y;
}
Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
References
cite-note-11. ↑ citerefpeter-coffee1996Peter Coffee (1996). "Tak test stands the test of time". PC Week. 13 (39).
cite-note-22. ↑ "Recursive Methods" by Elliotte Rusty Harold
cite-note-acornuser198606-33. ↑ citerefjohnson-davies1986Johnson-Davies, David (June 1986). "Six of the Best Against the Clock". Acorn User. pp. 179, 181–182. Retrieved 28 October 2020.
cite-note-acornuser198611-44. ↑ citerefjohnson-davies1986Johnson-Davies, David (November 1986). "Testing the Tak". Acorn User. pp. 197, 199. Retrieved 28 October 2020.
External links
• reference-mathworld-tak-functionciterefweissteinWeisstein, Eric W. "TAK Function". MathWorld.
• TAK Function Archived 2007-09-12 at the Wayback Machine